Aprendizado de Máquina I

Hugo Tremonte de Carvalho

hugo@dme.ufrj.br


11 KNN e árvores de classificação

\(K\) vizinhos mais próximos (KNN)

KNN - ideia

  • Relembrando: \(Y = r(\mathbf{X}) + \varepsilon\)
    • A relação sistemática entre \(\mathbf{X}\) e \(Y\) é “bem comportada”: \(\mathbf{X}\)’s próximos \(\Rightarrow\) \(Y\)’s semelhantes
  • Usar essa ideia para criar um estimador \(g\)
  • Diga-me com quem andas e te direi quem és

KNN - formalização

\[g(\mathbf{x}) = \mathrm{moda}_{i \in \mathcal{N}_{\mathbf{x}}^{(k)}} y_i,\] onde \(\mathcal{N}_{\mathbf{x}}^{(k)}\) é o conjunto dos índices das \(k\) observações mais próximas de \(\mathbf{x}\), ou seja, \[\mathcal{N}_{\mathbf{x}}^{(k)} = \left\{i \in \{1, \dots, n\} ~ \left| ~ d(\mathbf{x}_i, \mathbf{x}) \leq d_{\mathbf{x}}^k \right\}\right.,\] e \(d_{\mathbf{x}}^k\) representa a distância do \(k\)-ésimo vizinho mais próximo de \(\mathbf{x}\) para \(\mathbf{x}\).

KNN - propriedades

  • Hiperparâmetro \(k\) \(\Rightarrow\) validação cruzada
  • \(k\) alto \(\Rightarrow\) modelo simples
    • \(k \to \infty\) \(\Rightarrow\) \(g\) simples (linear?)
    • Viés alto, baixa variância
  • \(k\) pequeno \(\Rightarrow\) modelo mais complexo
    • Variância alta, viés baixo
    • Requer mais dados para ser mais fidedigno

KNN - Exemplo

KNN - Exemplo

scikit-learn - KNeighborClassifier

KNN = KNeighborsClassifier(n_neighbors = 1)
KNN.fit(X_train, y_train);

KNN - Exemplo

KNN = KNeighborsClassifier(n_neighbors = 5)
KNN.fit(X_train, y_train);

KNN - Exemplo

KNN = KNeighborsClassifier(n_neighbors = 50)
KNN.fit(X_train, y_train);

KNN - Exemplo

KNN = KNeighborsClassifier(n_neighbors = 300)
KNN.fit(X_train, y_train);

KNN - Observações

  • Hiperparâmetros podem (e devem!) ser otimizados através de validação cruzada
  • Classificador naturalmente multiclasse
  • Distâncias em alta dimensão podem impactar seu desempenho

Árvores de classificação

Formalizando

  • Partição do espaço das covariáveis
    • Regiões \(R_1, \dots, R_j\) distintas disjuntas
    • A predição para a resposta \(Y\) de uma observação \(\mathbf{x}\) que está na região \(k\) é a moda das respostas cujos respectivos \(\mathbf{x}\) também estão nessa região: \[g(\mathbf{x}) = \mathrm{moda}_{\{i ~ | ~ \mathbf{x}_i \in R_k\}} y_i\]

Criação da árvore

  • Métricas para determinar uma nova região \(R\):
    • Erro de classificação: \(\displaystyle E = 1 - \max_{c} \hat{p}_{R, c}\)
    • Índice de Gini: \(\displaystyle G = \sum_R\sum_{c \in \mathcal{C}} \hat{p}_{R, c}(1 - \hat{p}_{R, c})\)
    • Entropia: \(\displaystyle D = -\sum_{c \in \mathcal{C}} \hat{p}_{R, c}\log(\hat{p}_{R, c})\)
  • \(\hat{p}_{R, c}\) é a proporção de observações classificadas como sendo da classe \(c\) entre as que caem na região \(R\)
  • Prezar por árvores puras: cada folha contém observações de somente uma única classe

Árvores de classificação - Observações

  • Hiperparâmetros podem (e devem!) ser otimizados através de validação cruzada
  • Classificador naturalmente multiclasse
  • Poda análoga a árvores de regressão
  • Podem ser acopladas em bagging
  • Podem ser acopladas em florestas aleatórias

Árvores de classificação - Exemplo

Árvores de classificação - Exemplo

scikit-learn - DecisionTreeClassifier

DTC = DecisionTreeClassifier(max_depth = None, min_samples_leaf = 5)
DTC.fit(X_train, y_train);